package com.berchen.算法.贪心算法;

import java.util.*;

/**
 * 贪心算法：
 *  是指在每次对问题进行求解时，在每一步选择中都采取最好或者最优的选择，从而希望能够导致结果是最好或者最优的算法。
 * 广播站覆盖地区问题
 * 在已知广播站中找到广播站覆盖所有地区
 * 贪心算法可能不是最优解
 *
 * 思路：
 * 遍历所有广播电台（allArea），找到一个覆盖了最多未覆盖的地区的电台，（此电台可能包含已经覆盖的地区，但是没有关系）
 * 将这个电台加入到一个集合中，从allArea中去掉刚刚加入集合的电台覆盖的地区
 * 重复上面的操作 直到allArea的长度为0   说明找到了 电台覆盖所有地区的解决办法
 */
public class Greedy {
    public static void main(String[] args) {

        // 所有需要覆盖的地区
        Set<String> allArea= new HashSet<>();

        Map<String,Set<String>> diantai=new HashMap<>();
        Set<String> k1= new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        Set<String> k2= new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        Set<String> k3= new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        Set<String> k4= new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        Set<String> k5= new HashSet<>();
        k5.add("杭州");
        k5.add("大连");
        diantai.put("k1",k1);
        diantai.put("k2",k2);
        diantai.put("k3",k3);
        diantai.put("k4",k4);
        diantai.put("k5",k5);
        allArea.addAll(k1);
        allArea.addAll(k2);
        allArea.addAll(k3);
        allArea.addAll(k4);
        allArea.addAll(k5);


        List<String> greedy = greedy(diantai, allArea);
        System.out.println(greedy);
    }

    /**
     *
     * @param dt 电台map
     * @param allAreas 需要覆盖的所有区域
     * @return
     */
    public static List<String> greedy(Map<String,Set<String>> dt,Set<String> allAreas){

        // 保存电台的key
        List<String> result=new ArrayList<>();

        String key="";
        int jjLength=0;
        while (allAreas.size()>0){

            Set<String> jjSet = null;
            // 找到Map中覆盖地区最多的key
            for(Map.Entry<String,Set<String>> entry : dt.entrySet()){
                Set<String> jj = jj(allAreas, entry.getValue());
                // 每次都选择最好的  这就是贪心算法的特点
                if(jj.size()>jjLength){
                    jjLength=jj.size();
                    key=entry.getKey();
                    jjSet=jj;
                }
            }

            // 将key加入到result中
            if(!"".equals(key)) {
                result.add(key);
                key = "";
            }
            // 从allAreas 中去除 交集
            if(jjSet!=null) {
                allAreas.removeAll(jjSet);
                jjLength = 0;
            }
        }
        return  result;

    }

    /**
     * 求出两个Set的交集
     * @param set1
     * @param set2
     * @return
     */
    public static Set<String> jj(Set<String> set1,Set<String> set2){

        Set<String> result=new HashSet<>();
        result.addAll(set1);
        result.retainAll(set2);
        return result;
    }
}
